#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5 + 5;
inline int read(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return x*y;
}
int T,n,a[N],ans,dp[2005][2005][2];
int col[N];
void check(){
    int sum=0;
    for(int i=1;i<=n;++i){
        for(int j=i-1;j>=1;--j){
            if(col[i]==col[j]){
                if(a[i]==a[j]){
                    sum+=a[j];
                }
                break;
            }
        }
    }
    ans=max(ans,sum);
    return ;
}
void dfs(int cur){
    if(cur==n+1){
        check();
        return ;
    }
    col[cur]=1;
    dfs(cur+1);
    col[cur]=0;
    dfs(cur+1);
    return ;
}
void init(){
    ans=0;
    for(int i=1;i<=n;++i){
        col[i]=0;
    }
}
signed main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    T=read();
    while(T--){
        init();
        n=read();
        for(int i=1;i<=n;++i){
            a[i]=read();
        }
        if(n<=10){
            dfs(1);
            cout<<ans<<endl;
            continue;
        }
        if(n<=2000){
            for(int i=1;i<=n;++i){
                for(int j=1;j<=n;++j){
                    dp[i][j][0]=dp[i][j][1]=0;
                }
            }
            for(int i=2;i<=n;++i){
                for(int j=1;j<=n-i+1;++j){
                    if(a[j]==a[i+j-1]){
                        dp[j][i+j-1][0]=a[j];
                        dp[j][i+j-1][1]=dp[j][i+j-1][0]+dp[j+1][j+i-2][0];
                    }
                    for(int k=j;k<=i+j-1;++k){
                        dp[j][i+j-1][0]=max(dp[j][i+j-1][0],dp[j][k][0]+dp[k+1][i+j-1][0]);
                        dp[j][i+j-1][1]=max(dp[j][i+j-1][0],max(dp[j][i+j-1][1],dp[j][k][1]+dp[k+1][i+j-1][1]));
                        dp[j][i+j-1][1]=max(dp[j][i+j-1][1],max(dp[j][k][0]+dp[k+1][j+i-1][1],dp[j][k][1]+dp[k+1][i+j-1][0]));
                        ans=max(ans,max(dp[j][j+i-1][0],dp[j][j+i-1][1]));    
                    }
                }
            }
            cout<<ans<<endl;
        }
    }

    return 0;
}